#include "psearch.h"

int mpi_bsearch
(
 const void *key,      // address of the key on each process
 const void *base,     // address of the base on each process
 size_t num,              // number of the elements of the array
 size_t size,             // size of array element
 int (*compar)(const void *, const void *), //compare funciton pointer
 MPI_Comm comm,        // MPI communicator
 int ntds              // Number of OpenMP threads 
)              
{
  int mpi_rank; MPI_Comm_rank( comm, &mpi_rank);
  int mpi_size; MPI_Comm_size( comm, &mpi_size);
  int i;
  int keyid;

  double allkeys[mpi_size];  
  int    allkeysrank[mpi_size];
  int    other_id = 0;
  int    global_id = 0;
  int    keyfoundlocallyflag = 0;

  // Gather the keys from all processes
  MPI_Allgather((void *)key, 1, MPI_DOUBLE, allkeys, 1, MPI_DOUBLE, comm);

  for(i = 0; i < mpi_size; i++) 
    {
      allkeysrank[i] = i;
      //printf("allkeys[%i] is %f on process %i from process %i \n", i, allkeys[i], rank, allkeysrank[i]);
    }

  int buffer_size = 20 + MPI_BSEND_OVERHEAD;
  char buffer[buffer_size];
  MPI_Buffer_attach(buffer, buffer_size); 
  MPI_Status status;

  for(i = 0; i < mpi_size; i++)
    {

      keyid = omp_bsearch(&allkeys[i], base, num, size, compar, ntds);

      if(keyid >= 0)
	{
	  // Don't send messages to its own process 
	  if(i == mpi_rank)
	    {
	      keyfoundlocallyflag = 1;
	      global_id =  keyid + mpi_rank * num;
	      printf("\tkey %f from process %i is found on process %i, global_id is %d\n", allkeys[i], allkeysrank[i], mpi_rank, global_id);

	    }
	  else
	    {
	      other_id = keyid + mpi_rank * num;
	      printf("\tkey %f from process %i is found on process %i, global_id is %d\n", allkeys[i], allkeysrank[i], mpi_rank, other_id);
	      // Buffered send messages to other process 
	      MPI_Bsend(&other_id, 1, MPI_INT, allkeysrank[i], 0, comm);
	    }
	}
    }

  MPI_Buffer_detach(&buffer, &buffer_size);

  if( !keyfoundlocallyflag )
    // Receive message from other processes using wildcard
    MPI_Recv(&global_id, 1, MPI_INT, MPI_ANY_SOURCE, 0, comm, &status);
  
  return global_id;
}

int omp_bsearch
(
 const void* key,
 const void* base,
 size_t num,
 size_t size,
 int (*compar)(const void *, const void *), //compare funciton pointer
 int ntds                                   // Number of OpenMP threads 
)
{	

#pragma omp parallel
#pragma omp master
  omp_set_num_threads(ntds);

  ntds = 2;

  MESH me = initMesh(base, num, size, ntds);  //mesh information
  SPLT gs = initGlobalSplt(me);

  #if VERBOSE >= 1
  printMesh(me);
  printSplt(gs);
  #endif

  if (isKeyFound(key, compar, gs) == 0)
    return -1;

  SPLT ls = NULL;

  int iter = 0;
  int tdn;
  int i;
  int keyid;

  //printf("size %d and n %d\n", me->blk_sz, me->blk_num);
  // main loop to reduce the length of interval

  while (1)
    {
      #if VERBOSE >= 1
	printf("\n-------Iteration %i--------\n", iter);
	printMesh(me);
      #endif

      if (me->blk_num == 1) break;


#pragma omp parallel for private(ls, tdn), shared(key, gs, me)
      for(i = 0; i < me->blk_num; i++)
	{

	  tdn = omp_get_thread_num();

	  ls = initLocalSplt(me, i);   //initialize local splitters
	  //printSplt(ls);

	  if ( isKeyFound(key, compar, ls)) 
	    updateGlobalSplt(ls, gs);

	  deleteSplt(&ls);
	}

      updateMesh(gs, me);

      iter ++;
    }

  keyid = getKeyID(me, gs);

  deleteSplt(&gs);
  deleteMesh(&me);

  return keyid;
}

int getKeyID(MESH me, SPLT gs)
{
  int keyid = (gs->le - me->org_le)/ me->elem_sz;
  return keyid;
}
MESH initMesh(const void *base, int num, int size, int ntds)
{
  MESH me = (MESH) malloc (sizeof(struct mesh));
  me->org_le = (char *)base;
  me->org_re = (char *)base + (num-1) * size;
  me->le = me->org_le;
  me->re = me->org_re;
  me->elem_sz = size;
  me->ntds = ntds;

  /* ex. 
     num = 10, ntds = 4, 
     then sz = 3, n = 4 
     10 is paritioned as 
     3, 3, 3, 1*/

  me->blk_sz   = (int) ceil( (double)num/ntds) ;
  me->blk_num  = (int) ceil( (double)num/me->blk_sz) ;
  return me;
}
void printMesh(MESH me)
{
  printf("number of threads %i \n", me->ntds); 
  printf("number of blocks %i  \n", me->blk_num);
  printf("block size %i        \n", me->blk_sz);
  printf("left  end of mesh is %f \n", *((double*)me->le));
  printf("right end of mesh is %f \n", *((double*)me->re));
}

SPLT initLocalSplt(MESH me, int i)
{
  //  if(i >= ) return NULL;

  SPLT ls = (SPLT) malloc ( sizeof(struct splt) );
  ls->le = me->le + i * me->blk_sz * me->elem_sz;

  if (i == me->blk_num - 1)
    ls->re = me->re;
  else
    ls->re = me->le + (i+1) * me->blk_sz * me->elem_sz;

  ls->id = i;
  return ls;
}
void printSplt(SPLT s)
{

  double *lptr = (double *)s->le;
  double *rptr = (double *)s->re;
  printf("id %i le is %f re is %f \n", s->id, *lptr, *rptr );
}

int isKeyFound(const void* key, int (*compar)(const void *, const void *), SPLT ls)
{
  ls->lf = compar(ls->le, key);
  ls->rf = compar(ls->re, key);
  if ( (ls->lf == 0 || ls->lf == -1) && ls->rf == 1  ){
    #if VERBOSE >= 1
    printf("Keys found in splitter %i\n", ls->id);
    #endif
    return 1;}
  else 
    return 0;

}

SPLT initGlobalSplt(MESH me)
{
  SPLT gs = (SPLT) malloc (sizeof(struct splt));
  gs->le = me->le;
  gs->re = me->re;
  gs->id = -1;
  return gs;
}

int updateMesh(SPLT gs, MESH me)
{
  me->le = gs->le;
  me->re = gs->re;
  int num = (gs->re - gs->le) / me->elem_sz;
  me->blk_sz   = (int) ceil( (double)num/me->ntds) ;
  me->blk_num  = (int) ceil( (double)num/me->blk_sz) ;
  return 0;
}

int updateGlobalSplt(SPLT ls, SPLT gs)
{
  gs->le = ls->le;
  gs->re = ls->re;
  gs->id = ls->id;
  return 0;
}

int userComparOperator( const void *x1, const void *x2){
	double *a = (double *) x1;
	double *b = (double *) x2;

	if (*a > *b) 	  return 1;
	else if(*a < *b) return -1;
	else return 0;
}

void deleteSplt(SPLT *s)  { free( *s);  }
void deleteMesh(MESH *me) { free (*me); }
